{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum BST in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索子树的最大键值和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵以 <code>root</code> 为根的 <strong>二叉树</strong> ，请你返回 <strong>任意</strong> 二叉搜索子树的最大键值和。</p>\n",
    "\n",
    "<p>二叉搜索树的定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>任意节点的左子树中的键值都 <strong>小于</strong> 此节点的键值。</li>\n",
    "\t<li>任意节点的右子树中的键值都 <strong>大于</strong> 此节点的键值。</li>\n",
    "\t<li>任意节点的左子树和右子树都是二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_1_1709.png\" style=\"height: 250px; width: 320px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>键值为 3 的子树是和最大的二叉搜索树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_2_1709.png\" style=\"height: 180px; width: 134px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,3,null,1,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>键值为 2 的单节点子树是和最大的二叉搜索树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [-4,-2,-5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>所有节点键值都为负数，和最大的二叉搜索树为空。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,3,null,6,3]\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树有 <code>1</code> 到 <code>40000</code> 个节点。</li>\n",
    "\t<li>每个节点的键值在 <code>[-4 * 10^4 , 4 * 10^4]</code> 之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-bst-in-binary-tree](https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-bst-in-binary-tree](https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]', '[4,3,null,1,2]', '[-4,-2,-5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return float('inf'), float('-inf'), 0\n",
    "            l_small, l_big, l_tot = dfs(node.left)\n",
    "            r_small, r_big, r_tot = dfs(node.right)\n",
    "            if l_big < node.val < r_small:\n",
    "                self.ans = max(self.ans, node.val + l_tot + r_tot)\n",
    "                return min(l_small, node.val), max(r_big, node.val), node.val + l_tot + r_tot\n",
    "            return float('-inf'), float('inf'), 0\n",
    "    \n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxSumBST(self, root):\n",
    "        def levelOrder(root):\n",
    "            if not root: return []\n",
    "            cur = root\n",
    "            gray = [cur]\n",
    "            black = []\n",
    "            while gray:\n",
    "                black.append(gray[0])\n",
    "                if gray[0].left: gray.append(gray[0].left)\n",
    "                if gray[0].right: gray.append(gray[0].right)\n",
    "                gray.pop(0)\n",
    "            return black\n",
    "        def inorderValue(rt):\n",
    "            if not rt: return []\n",
    "            Res = inorderValue(rt.left) + [rt.val] + inorderValue(rt.right)\n",
    "            return Res\n",
    "        def isBST(lst):\n",
    "            cur = lst[0]\n",
    "            for i in range(1, len(lst)):\n",
    "                if lst[i] <= cur: return False\n",
    "                cur = max(lst[i], cur)\n",
    "            return True\n",
    "        if not root:\n",
    "            return 0\n",
    "        nodelst = levelOrder(root)\n",
    "        value = 0\n",
    "        bad = set()\n",
    "        good = dict()\n",
    "        for node in nodelst[::-1]:\n",
    "            if node.left in bad or node.right in bad: \n",
    "                bad.add(node)\n",
    "            elif node.left in good and node.right in good \\\n",
    "                and node.val > good[node.left][1] and node.val < good[node.right][2]:\n",
    "                good[node] = (node.val + good[node.left][0] + good[node.right][0], \n",
    "                    good[node.right][2], good[node.left][1])\n",
    "                value = max(value, good[node][0])\n",
    "            elif not node.left and node.right in good and node.val < good[node.right][2]:\n",
    "                good[node] = (node.val + good[node.right][0], good[node.right][1], node.val)\n",
    "                value = max(value, good[node][0])\n",
    "            elif not node.right and node.left in good and node.val > good[node.left][1]:\n",
    "                good[node] = (node.val + good[node.left][0], node.val, good[node.left][2])\n",
    "                value = max(value, good[node][0])\n",
    "            elif not node.right and not node.left:\n",
    "                good[node] = (node.val, node.val, node.val)\n",
    "                value = max(value, good[node][0])\n",
    "            else:\n",
    "                bad.add(node)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        # 校验是不是二叉搜索树\n",
    "        # 二叉搜索树的特性，左子树中的最小值，最大值，右子树中的最小值，最大值。\n",
    "        # 当前的节点值，要大于左子树中的最大值，小于右子树中的最小值。\n",
    "        # 如果当前节点已经不是二叉树，那么父节点已经不用再计算\n",
    "\n",
    "        nodes = [root]\n",
    "        plevel = nodes\n",
    "        node2parent = {root: None}\n",
    "        while True:\n",
    "            clevel = []\n",
    "            for node in plevel:\n",
    "                if node.left:\n",
    "                    clevel.append(node.left)\n",
    "                    node2parent[node.left] = node\n",
    "                if node.right:\n",
    "                    clevel.append(node.right)\n",
    "                    node2parent[node.right] = node\n",
    "            if not clevel:\n",
    "                break\n",
    "            plevel = clevel\n",
    "            nodes.extend(clevel)\n",
    "        \n",
    "        invalid = set()\n",
    "        res = 0\n",
    "        cache = {}\n",
    "\n",
    "        for idx in range(len(nodes) - 1, -1, -1):\n",
    "            node = nodes[idx]\n",
    "            if node in invalid:\n",
    "                continue\n",
    "            if node.left and node.right:\n",
    "                lmax, lmin, lsum = cache[node.left]\n",
    "                rmax, rmin, rsum = cache[node.right]\n",
    "                if lmax < node.val < rmin:\n",
    "                    s = lsum + rsum + node.val\n",
    "                    cache[node] = rmax, lmin, s\n",
    "                    if s > res:\n",
    "                        res = s\n",
    "                    continue\n",
    "            elif node.left:\n",
    "                lmax, lmin, lsum = cache[node.left]\n",
    "                if lmax < node.val:\n",
    "                    s = lsum + node.val\n",
    "                    cache[node] = node.val, lmin, s\n",
    "                    if s > res:\n",
    "                        res = s\n",
    "                    continue\n",
    "            elif node.right:\n",
    "                rmax, rmin, rsum = cache[node.right]\n",
    "                if node.val < rmin:\n",
    "                    s = rsum + node.val\n",
    "                    cache[node] = rmax, node.val, s\n",
    "                    if s > res:\n",
    "                        res = s\n",
    "                    continue\n",
    "            else:\n",
    "                cache[node] = node.val, node.val, node.val\n",
    "                if node.val > res:\n",
    "                    res = node.val\n",
    "                continue\n",
    "            while node:\n",
    "                invalid.add(node)\n",
    "                node = node2parent[node]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 左子节点合法？\n",
    "        ## 不合法则父节点也不合法\n",
    "        ## 右子节点合法？\n",
    "        ### 父节点大于左最大和右最小，则父节点合法\n",
    "        ### 反之不合法\n",
    "        node_to_range = {}\n",
    "        res = 0\n",
    "        st = [root]\n",
    "        while st:\n",
    "            node = st[-1]\n",
    "            s = node.val\n",
    "            r = [s, s]\n",
    "            if node.left is not None:\n",
    "                l_range = node_to_range.get(node.left)\n",
    "                if node_to_range.get(node.left) is None:\n",
    "                    st.append(node.left)\n",
    "                    continue\n",
    "                if l_range == [] or l_range[1] >= node.val:\n",
    "                    r = []\n",
    "                else:\n",
    "                    r = [l_range[0], node.val]\n",
    "                s += node.left.sum\n",
    "            if node.right is not None:\n",
    "                r_range = node_to_range.get(node.right)\n",
    "                if r_range is None:\n",
    "                    st.append(node.right)\n",
    "                    continue\n",
    "                if r_range == [] or r_range[0] <= node.val or r == []:\n",
    "                    r = []\n",
    "                else:\n",
    "                    r[1] = r_range[1]\n",
    "                s += node.right.sum\n",
    "            node.sum = s if r else 0\n",
    "            node_to_range[node] = r\n",
    "            res = max(res, node.sum)\n",
    "            st.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        #为避免递归，树转为层次list，记录父节点，root在最后\n",
    "        #节点、父节点、和、最小、最大，若不为二叉搜索树，和为None\n",
    "        l = [[root]]\n",
    "        \n",
    "        while 1:\n",
    "            now = []\n",
    "            for n in l[0]:\n",
    "                if n.left:\n",
    "                    now.append(n.left)\n",
    "                if n.right:\n",
    "                    now.append(n.right)\n",
    "            \n",
    "            if now:\n",
    "                l.insert(0, now)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        self.ret = 0\n",
    "        \n",
    "        def do(n):\n",
    "            if n.left:\n",
    "                if n.left.he == None:\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "                if n.right:\n",
    "                    if n.right.he == None:\n",
    "                        n.he = None\n",
    "                        return\n",
    "                    \n",
    "                    if n.left.max < n.val < n.right.min:\n",
    "                        n.he = n.left.he + n.val + n.right.he\n",
    "                        n.min = n.left.min\n",
    "                        n.max = n.right.max\n",
    "\n",
    "                        self.ret = max(self.ret, n.he)\n",
    "                        return\n",
    "\n",
    "                    n.he = None\n",
    "                    return\n",
    "                else:\n",
    "                    if n.left.max < n.val:\n",
    "                        n.he = n.left.he + n.val\n",
    "                        n.min = n.left.min\n",
    "                        n.max = n.val\n",
    "\n",
    "                        self.ret = max(self.ret, n.he)\n",
    "                        return\n",
    "\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "            if n.right:\n",
    "                if n.right.he == None:\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "                if n.val < n.right.min:\n",
    "                    n.he = n.val + n.right.he\n",
    "                    n.min = n.val\n",
    "                    n.max = n.right.max\n",
    "\n",
    "                    self.ret = max(self.ret, n.he)\n",
    "                    return\n",
    "\n",
    "                n.he = None\n",
    "                return\n",
    "\n",
    "            #没有子节点\n",
    "            n.he = n.min = n.max = n.val\n",
    "            self.ret = max(self.ret, n.he)\n",
    "\n",
    "        #从最底开始递归\n",
    "        for one in l:\n",
    "            for n in one:\n",
    "                do(n)\n",
    "\n",
    "        return self.ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        levels: List[Set[TreeNode]] = [{root}]\n",
    "        node2parent = {}\n",
    "        while True:\n",
    "            up_one_level = levels[-1]\n",
    "            t = set()\n",
    "            for n in up_one_level:\n",
    "                if n.left:\n",
    "                    t.add(n.left)\n",
    "                    node2parent[n.left] = n\n",
    "                if n.right:\n",
    "                    t.add(n.right)\n",
    "                    node2parent[n.right] = n\n",
    "            if t:\n",
    "                levels.append(t)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        res = 0\n",
    "        Res = namedtuple('Res', 'is_tree max min sum')\n",
    "        d: Dict[TreeNode, Res] = {}\n",
    "        invalid = set()\n",
    "        for level in levels[::-1]:\n",
    "            tinvalid = set()\n",
    "            for node in level:\n",
    "                if node in invalid:\n",
    "                    tinvalid.add(node2parent.get(node))\n",
    "                    continue\n",
    "                if node.left and node.right:\n",
    "                    lres, rres = d[node.left], d[node.right]\n",
    "                    if lres.is_tree and rres.is_tree:\n",
    "                        if lres.max < node.val < rres.min:\n",
    "                            s = lres.sum + rres.sum + node.val\n",
    "                            d[node] = Res(True, rres.max, lres.min, s)\n",
    "                            res = max(res, s)\n",
    "                            continue\n",
    "                    tinvalid.add(node2parent.get(node))\n",
    "                elif node.left:\n",
    "                    lres = d[node.left]\n",
    "                    if lres.is_tree:\n",
    "                        if node.val > lres.max:\n",
    "                            s = (lres.sum + node.val)\n",
    "                            d[node] = Res(True, node.val, lres.min, s)\n",
    "                            res = max(res, s)\n",
    "                            continue\n",
    "                    tinvalid.add(node2parent.get(node))\n",
    "                elif node.right:\n",
    "                    rres = d[node.right]\n",
    "                    if rres.is_tree:\n",
    "                        if node.val < rres.min:\n",
    "                            s = (rres.sum + node.val)\n",
    "                            d[node] = Res(True, rres.max, node.val, s)\n",
    "                            res = max(res, s)\n",
    "                            continue\n",
    "                    tinvalid.add(node2parent.get(node))\n",
    "                else:\n",
    "                    d[node] = Res(True, node.val, node.val, node.val)\n",
    "                    res = max(res, node.val)\n",
    "            invalid = tinvalid\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        #为避免递归，树转为层次list，记录父节点，root在最后\n",
    "        #节点、父节点、和、最小、最大，若不为二叉搜索树，和为None\n",
    "        l = [[root]]\n",
    "        \n",
    "        while 1:\n",
    "            now = []\n",
    "            for n in l[0]:\n",
    "                if n.left:\n",
    "                    now.append(n.left)\n",
    "                if n.right:\n",
    "                    now.append(n.right)\n",
    "            \n",
    "            if now:\n",
    "                l.insert(0, now)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        self.ret = 0\n",
    "        \n",
    "        def do(n):\n",
    "            if n.left:\n",
    "                if n.left.he == None:\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "                if n.right:\n",
    "                    if n.right.he == None:\n",
    "                        n.he = None\n",
    "                        return\n",
    "                    \n",
    "                    if n.left.max < n.val < n.right.min:\n",
    "                        n.he = n.left.he + n.val + n.right.he\n",
    "                        n.min = n.left.min\n",
    "                        n.max = n.right.max\n",
    "\n",
    "                        self.ret = max(self.ret, n.he)\n",
    "                        return\n",
    "\n",
    "                    n.he = None\n",
    "                    return\n",
    "                else:\n",
    "                    if n.left.max < n.val:\n",
    "                        n.he = n.left.he + n.val\n",
    "                        n.min = n.left.min\n",
    "                        n.max = n.val\n",
    "\n",
    "                        self.ret = max(self.ret, n.he)\n",
    "                        return\n",
    "\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "            if n.right:\n",
    "                if n.right.he == None:\n",
    "                    n.he = None\n",
    "                    return\n",
    "\n",
    "                if n.val < n.right.min:\n",
    "                    n.he = n.val + n.right.he\n",
    "                    n.min = n.val\n",
    "                    n.max = n.right.max\n",
    "\n",
    "                    self.ret = max(self.ret, n.he)\n",
    "                    return\n",
    "\n",
    "                n.he = None\n",
    "                return\n",
    "\n",
    "            #没有子节点\n",
    "            n.he = n.min = n.max = n.val\n",
    "            self.ret = max(self.ret, n.he)\n",
    "\n",
    "        #从最底开始递归\n",
    "        for one in l:\n",
    "            for n in one:\n",
    "                do(n)\n",
    "\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        from collections import deque\n",
    "\n",
    "        nodeQueue = deque()\n",
    "        nodeQueue.append(root)\n",
    "        nodes = []\n",
    "        while nodeQueue:\n",
    "            curNode = nodeQueue.popleft()\n",
    "            if curNode:\n",
    "                nodes.append(curNode)\n",
    "                nodeQueue.append(curNode.left)\n",
    "                nodeQueue.append(curNode.right)\n",
    "\n",
    "        result = 0\n",
    "        for node in reversed(nodes):\n",
    "            node.sum, node.min, node.max = node.val, node.val, node.val\n",
    "            node.isSearchTree = True\n",
    "            if node.left:\n",
    "                if not node.left.isSearchTree or node.val <= node.left.max:\n",
    "                    node.isSearchTree = False\n",
    "                else:\n",
    "                    node.sum += node.left.sum\n",
    "                    node.min = node.left.min\n",
    "            if node.right:\n",
    "                if not node.isSearchTree or not node.right.isSearchTree or node.val >= node.right.min:\n",
    "                    node.isSearchTree = False\n",
    "                else:\n",
    "                    node.sum += node.right.sum\n",
    "                    node.max = node.right.max\n",
    "            if node.isSearchTree:\n",
    "                result = max(result, node.sum)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isBST(self, node):\n",
    "        if node is None:\n",
    "            return True\n",
    "\n",
    "        if hasattr(node, \"isBST\"):\n",
    "            return node.isBST\n",
    "\n",
    "        if (node.left is None) and (node.right is None):\n",
    "            node.isBST = True\n",
    "            return node.isBST\n",
    "\n",
    "        if not self.isBST(node.left) or  not self.isBST(node.right):\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "\n",
    "        if node.left is not None and self.maxVal(node.left) >= node.val:\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "        \n",
    "        if node.right is not None and self.minVal(node.right) <= node.val:\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "\n",
    "        node.isBST = True\n",
    "        return node.isBST\n",
    "\n",
    "    def minVal(self, node):\n",
    "        if hasattr(node, \"minVal\"):\n",
    "            return node.minVal\n",
    "\n",
    "        val = node.val\n",
    "        if node.left is not None and self.minVal(node.left) < val:\n",
    "            val = self.minVal(node.left)\n",
    "        if node.right is not None and self.minVal(node.right) < val:\n",
    "            val = self.minVal(node.right)\n",
    "\n",
    "        node.minVal = val\n",
    "        return node.minVal\n",
    "\n",
    "    def maxVal(self, node):\n",
    "        if hasattr(node, \"maxVal\"):\n",
    "            return node.maxVal\n",
    "\n",
    "        val = node.val\n",
    "        if node.left is not None and self.maxVal(node.left) > val:\n",
    "            val = self.maxVal(node.left)\n",
    "        if node.right is not None and self.maxVal(node.right) > val:\n",
    "            val = self.maxVal(node.right)\n",
    "\n",
    "        node.maxVal = val\n",
    "        return node.maxVal\n",
    "\n",
    "    def maxSumValue(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "\n",
    "        if hasattr(node, \"maxSumValue\"):\n",
    "            return node.maxSumValue\n",
    "\n",
    "        val = self.maxSumValue(node.left) + self.maxSumValue(node.right) + node.val \n",
    "\n",
    "        node.maxSumValue = val\n",
    "        return node.maxSumValue\n",
    "\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        # 采用后序遍历的方式，获取每一个节点的子树和，并判断子树是否是一个搜索树\n",
    "\n",
    "        stack = []\n",
    "        node = root\n",
    "        maxVal = 0\n",
    "        preRight = None\n",
    "\n",
    "        while node or stack:\n",
    "            # 每一个节点的左子树\n",
    "            while node:\n",
    "                #print(\"-->Enstack a node %d\" % node.val)\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "\n",
    "            # 如果右子树未遍历过，遍历右子树\n",
    "            node = stack.pop(-1)\n",
    "            #print(\"-->pop a node %d\" % node.val)\n",
    "            if node.right is not None and preRight != node.right:\n",
    "                stack.append(node)\n",
    "                #print(\"-->Enstack a previous node %d\" % node.val)\n",
    "                node = node.right\n",
    "            # 左右子树都已访问过，访问当前节点\n",
    "            else:\n",
    "                #print(\"Node %d: isBST = %s, maxVal = %d, oldMaxVal = %d. maxVal = %d, minVal = %d\"\n",
    "                #     % (node.val, str(self.isBST(node)), self.maxSumValue(node), maxVal, \n",
    "                #        self.maxVal(node), self.minVal(node)))\n",
    "                if self.isBST(node):\n",
    "                    maxVal = max(maxVal, self.maxSumValue(node))\n",
    "                    #print(\"----->Node %d is BTS, maxVal = %d\" % (node.val, self.maxSumValue(node)))\n",
    "\n",
    "                preRight = node\n",
    "                node = None\n",
    "        print(\"max val is \", maxVal)\n",
    "        return maxVal\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isBST(self, node):\n",
    "        if node is None:\n",
    "            return True\n",
    "\n",
    "        if hasattr(node, \"isBST\"):\n",
    "            return node.isBST\n",
    "\n",
    "        if (node.left is None) and (node.right is None):\n",
    "            node.isBST = True\n",
    "            return node.isBST\n",
    "\n",
    "        if not self.isBST(node.left) or  not self.isBST(node.right):\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "\n",
    "        if node.left is not None and self.maxVal(node.left) >= node.val:\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "        \n",
    "        if node.right is not None and self.minVal(node.right) <= node.val:\n",
    "            node.isBST = False\n",
    "            return node.isBST\n",
    "\n",
    "        node.isBST = True\n",
    "        return node.isBST\n",
    "\n",
    "    def minVal(self, node):\n",
    "        if hasattr(node, \"minVal\"):\n",
    "            return node.minVal\n",
    "\n",
    "        val = node.val\n",
    "        if node.left is not None and self.minVal(node.left) < val:\n",
    "            val = self.minVal(node.left)\n",
    "        if node.right is not None and self.minVal(node.right) < val:\n",
    "            val = self.minVal(node.right)\n",
    "\n",
    "        node.minVal = val\n",
    "        return node.minVal\n",
    "\n",
    "    def maxVal(self, node):\n",
    "        if hasattr(node, \"maxVal\"):\n",
    "            return node.maxVal\n",
    "\n",
    "        val = node.val\n",
    "        if node.left is not None and self.maxVal(node.left) > val:\n",
    "            val = self.maxVal(node.left)\n",
    "        if node.right is not None and self.maxVal(node.right) > val:\n",
    "            val = self.maxVal(node.right)\n",
    "\n",
    "        node.maxVal = val\n",
    "        return node.maxVal\n",
    "\n",
    "    def maxSumValue(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "\n",
    "        if hasattr(node, \"maxSumValue\"):\n",
    "            return node.maxSumValue\n",
    "\n",
    "        val = self.maxSumValue(node.left) + self.maxSumValue(node.right) + node.val \n",
    "\n",
    "        node.maxSumValue = val\n",
    "        return node.maxSumValue\n",
    "\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        # 采用后序遍历的方式，获取每一个节点的子树和，并判断子树是否是一个搜索树\n",
    "\n",
    "        stack = []\n",
    "        node = root\n",
    "        maxVal = 0\n",
    "        preRight = None\n",
    "\n",
    "        while node or stack:\n",
    "            # 每一个节点的左子树\n",
    "            while node:\n",
    "                #print(\"-->Enstack a node %d\" % node.val)\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "\n",
    "            # 如果右子树未遍历过，遍历右子树\n",
    "            node = stack.pop(-1)\n",
    "            #print(\"-->pop a node %d\" % node.val)\n",
    "            if node.right is not None and preRight != node.right:\n",
    "                stack.append(node)\n",
    "                node = node.right\n",
    "            # 左右子树都已访问过，访问当前节点\n",
    "            else:\n",
    "\n",
    "                if self.isBST(node):\n",
    "                    maxVal = max(maxVal, self.maxSumValue(node))\n",
    "\n",
    "                preRight = node\n",
    "                node = None\n",
    "        return maxVal\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.max = 4 * 10 ** 4 + 1\n",
    "        self.dfs(root)\n",
    "        \n",
    "        return self.res\n",
    "        \n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left_sum = self.dfs(root.left)\n",
    "        right_sum = self.dfs(root.right)\n",
    "        if left_sum != self.max and right_sum != self.max and (root.left is None or root.left.val < root.val) and (root.right is None or root.right.val > root.val):\n",
    "            sum = left_sum + right_sum + root.val\n",
    "            self.res = max(self.res, sum)\n",
    "            return sum\n",
    "        return self.max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.max_value = 0\n",
    "        self.helper(root)\n",
    "        return self.max_value\n",
    "        \n",
    "    def helper(self, root):\n",
    "        # 返回三个变量\n",
    "        # 分别为【以当前节点为根节点的二叉搜索树的键值和】,【上界】,【下界】\n",
    "        if not root:\n",
    "            return 0, 5e4, -5e4 \n",
    "        value1, min_value1, max_value1 = self.helper(root.left)\n",
    "        value2, min_value2, max_value2 = self.helper(root.right)         \n",
    "        if max_value1 < root.val and min_value2 > root.val: \n",
    "            # 满足二叉搜索树条件\n",
    "            self.max_value = max(self.max_value, value1 + value2 + root.val)\n",
    "            return value1 + value2 + root.val, min(min_value1, root.val), max(max_value2, root.val)\n",
    "        # 说明该节点无法构成二叉搜索树，返回恒不成立的条件，一直返回到顶\n",
    "        return root.val, -5e4, 5e4  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.max_value = 0\n",
    "        self.helper(root)\n",
    "        return self.max_value\n",
    "\n",
    "    def helper(self, root):\n",
    "        # 返回三个变量\n",
    "        # 分别为【以当前节点为根节点的二叉搜索树的键值和】,【上界】,【下界】\n",
    "        if not root:\n",
    "            return 0, 5e4, -5e4\n",
    "        value1, min_value1, max_value1 = self.helper(root.left)\n",
    "        value2, min_value2, max_value2 = self.helper(root.right)\n",
    "        if max_value1 < root.val and min_value2 > root.val:\n",
    "            # 满足二叉搜索树条件\n",
    "            self.max_value = max(self.max_value, value1 + value2 + root.val)\n",
    "            return value1 + value2 + root.val, min(min_value1, root.val), max(max_value2, root.val)\n",
    "        # 说明该节点无法构成二叉搜索树，返回恒不成立的条件，一直返回到顶\n",
    "        return root.val, -5e4, 5e4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.max = float('inf')\n",
    "        self.min = float('-inf')\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return self.max, self.min, 0\n",
    "        l_min, l_max, l_sum = self.dfs(root.left)\n",
    "        r_min, r_max, r_sum = self.dfs(root.right)\n",
    "        if l_max < root.val and r_min > root.val:\n",
    "            if r_max == self.min:\n",
    "                r_max = root.val\n",
    "            if l_min == self.max:\n",
    "                l_min = root.val\n",
    "            curr_sum = l_sum + r_sum + root.val\n",
    "            self.res = max(self.res, curr_sum)\n",
    "            return l_min, r_max, curr_sum\n",
    "\n",
    "        return self.min, self.max, 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_sum = 0\n",
    "\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.is_BST(root)\n",
    "        return self.max_sum\n",
    "\n",
    "    def get_min(self, root: TreeNode):\n",
    "        # 返回BST最左子树的值（最小的值）\n",
    "        while root.left is not None:\n",
    "            root = root.left\n",
    "        return root.val\n",
    "\n",
    "    def get_max(self, root: TreeNode):\n",
    "        # 返回BST最右子树的值（最大的值）\n",
    "        while root.right is not None:\n",
    "            root = root.right\n",
    "        return root.val\n",
    "\n",
    "    def is_BST(self, root: TreeNode):\n",
    "        # 判断以root为根的结点是否为二叉搜索树，并计算每个二叉搜索树的和，并与最大的进行比较\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left_sum = self.is_BST(root.left)\n",
    "        right_sum = self.is_BST(root.right)\n",
    "        # -1 表示 非二叉搜索树\n",
    "        if left_sum is False or right_sum is False:\n",
    "            return False\n",
    "        # 判断是否为二叉搜索树\n",
    "        if root.left is not None:\n",
    "            if self.get_max(root.left) >= root.val:\n",
    "                return False\n",
    "        if root.right is not None:\n",
    "            if self.get_min(root.right) <= root.val:\n",
    "                return False\n",
    "        res = left_sum + right_sum + root.val\n",
    "        if res > self.max_sum:\n",
    "            self.max_sum = res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: TreeNode) -> int:\n",
    "        self.max_sum = 0\n",
    "        self.isValidBST(root)\n",
    "        return self.max_sum\n",
    "\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True, 0\n",
    "\n",
    "\n",
    "        left_flag, left_sum = self.isValidBST(root.left)\n",
    "        right_flag, right_sum = self.isValidBST(root.right)\n",
    "        if left_flag and right_flag:\n",
    "            if self.getMax(root.left) < root.val < self.getMin(root.right):\n",
    "                sum = left_sum + root.val + right_sum\n",
    "                if sum > self.max_sum:\n",
    "                    self.max_sum = sum\n",
    "                return True, sum\n",
    "\n",
    "        return False, left_sum + root.val + right_sum\n",
    "\n",
    "    def getMax(self, root):\n",
    "        if root is None:\n",
    "            return -2**32\n",
    "\n",
    "        while root.right is not None:\n",
    "            root = root.right\n",
    "        return root.val\n",
    "\n",
    "    def getMin(self, root):\n",
    "        if root is None:\n",
    "            return 2**32\n",
    "\n",
    "        while root.left is not None:\n",
    "            root = root.left\n",
    "        return root.val\n",
    "\n",
    "    def getSum(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        return self.getSum(root.left) + root.val + self.getSum(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def is_BST(self, root, min_val, max_val):\n",
    "        if not root:\n",
    "            return True \n",
    "        return min_val<root.val<max_val and self.is_BST(root.left, min_val, root.val) and self.is_BST(root.right, root.val, max_val)\n",
    "\n",
    "    def tree_sum(self, root):\n",
    "        if not root:\n",
    "            return 0 \n",
    "        current_tree_sum = root.val + self.tree_sum(root.left) + self.tree_sum(root.right)\n",
    "        self.res = max(self.res, current_tree_sum)\n",
    "        return current_tree_sum\n",
    "    \n",
    "    def find_max_sum(self, root):\n",
    "        if self.is_BST(root, float(\"-inf\"), float(\"inf\")):\n",
    "            self.tree_sum(root)\n",
    "            return \n",
    "        self.find_max_sum(root.left)\n",
    "        self.find_max_sum(root.right)\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.find_max_sum(root)\n",
    "        return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        _ = self.traverse(root)\n",
    "        return self.ans\n",
    "\n",
    "    def traverse(self, node):\n",
    "        '''\n",
    "        BST or not | min | max | val sum\n",
    "        '''\n",
    "        # if not node.left and not node.right:\n",
    "        #     return True, node.val, node.val, node.val\n",
    "        if not node:\n",
    "            return True, None, None, 0\n",
    "        left_bst, left_min, left_max, left_sum = self.traverse(node.left)\n",
    "        right_bst, right_min, right_max, right_sum = self.traverse(node.right)\n",
    "        # decide whether current node is a BST\n",
    "        if left_bst and right_bst and (left_max is None or node.val > left_max) and (right_min is None or node.val < right_min):\n",
    "            cur_sum = left_sum+right_sum+node.val\n",
    "            self.ans = max(cur_sum, self.ans)\n",
    "            return True, left_min if left_min is not None else node.val, right_max if right_max is not None else node.val, cur_sum\n",
    "        return False, None, None, max(left_sum, right_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.maxSum = 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.maxSum\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            #['是否为BST','子树的最小值','子树的最大值','子树的建值']\n",
    "            return [1,100000000,-100000000,0]\n",
    "        \n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        res = list(range(4))\n",
    "        if left[0] == 1 and right[0] == 1 and left[2] < root.val and right[1] > root.val:\n",
    "            res[0] = 1\n",
    "            res[1] = min(left[1],root.val)\n",
    "            res[2] = max(right[2],root.val)\n",
    "            res[3] = left[3] + right[3] + root.val\n",
    "            self.maxSum = max(res[3], self.maxSum)\n",
    "        else:\n",
    "            res[0] = 0\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import namedtuple\n",
    "result = namedtuple(\"Result\", \"is_BST, min_value, max_value, sum_value\", defaults=(False, 1e5, -1e5, 0))\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_sum = 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.max_sum\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return result(True)\n",
    "\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "\n",
    "        if left.is_BST and right.is_BST and root.val > left.max_value and root.val < right.min_value:\n",
    "            # 注意返回值中的最小值和最大值一定要和子树做比较，因为对于叶子结点来说我们设置的默认值分别是极限最大值和极限最小值。\n",
    "            sum_value = left.sum_value + right.sum_value + root.val\n",
    "            self.max_sum = max(self.max_sum, sum_value)\n",
    "            return result(\n",
    "                True, \n",
    "                min(left.min_value, root.val), \n",
    "                max(right.max_value, root.val), \n",
    "                sum_value\n",
    "                )\n",
    "        else:\n",
    "            return result()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "\n",
    "    def maxSumBST(self, root:TreeNode):\n",
    "        self._maxSumBST(root)\n",
    "        return self.max\n",
    "\n",
    "    def _maxSumBST(self, node):\n",
    "        if node.left is None and node.right is None:\n",
    "            self.to_max(node.val)\n",
    "            return {\"sum\": node.val, \"min\": node.val, \"max\": node.val}\n",
    "        elif node.left is None and node.right is not None:\n",
    "            valid_right = self._maxSumBST(node.right)\n",
    "            if valid_right is not None and node.val < valid_right['min']:\n",
    "                new_sum = valid_right['sum'] + node.val\n",
    "                self.to_max(new_sum)\n",
    "                return {\"sum\": new_sum, \"min\": node.val, \"max\": valid_right['max']}\n",
    "        elif node.left is not None and node.right is None:\n",
    "            valid_left = self._maxSumBST(node.left)\n",
    "            if valid_left is not None and node.val > valid_left['max']:\n",
    "                new_sum = valid_left['sum'] + node.val\n",
    "                self.to_max(new_sum)\n",
    "                return {\"sum\": new_sum, \"min\": valid_left['min'], \"max\": node.val}\n",
    "        else:\n",
    "            valid_right = self._maxSumBST(node.right)\n",
    "            valid_left = self._maxSumBST(node.left)\n",
    "            if valid_right is not None and valid_left is not None and valid_left['max'] < node.val < valid_right['min']:\n",
    "                new_sum = node.val + valid_right['sum'] + valid_left['sum']\n",
    "                self.to_max(new_sum)\n",
    "                return {\"sum\": new_sum, \"min\": valid_left['min'], \"max\": valid_right['max']}\n",
    "\n",
    "    def to_max(self, val):\n",
    "        if val > self.max:\n",
    "            self.max = val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root.left and not root.right: \n",
    "                res = max(res, root.val)\n",
    "                return 1, root.val, root.val, root.val\n",
    "            elif not root.left:\n",
    "                r = dfs(root.right)\n",
    "                if r[0] and root.val < r[2]:\n",
    "                    x = r[1] + root.val\n",
    "                    res = max(res, x)\n",
    "                    return 1, x, root.val, r[3]\n",
    "            elif not root.right:\n",
    "                l = dfs(root.left)\n",
    "                if l[0] and l[-1] < root.val:\n",
    "                    x = l[1] + root.val\n",
    "                    res = max(res, x)\n",
    "                    return 1, x, l[2], root.val\n",
    "            else:\n",
    "                l, r = dfs(root.left), dfs(root.right)\n",
    "                if l[0] and r[0] and l[-1] < root.val < r[2]:\n",
    "                    x = root.val + l[1] + r[1]\n",
    "                    res = max(res, x)\n",
    "                    return 1, x, l[2], r[3]\n",
    "            return 0, 0, 0, 0\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root == None:\n",
    "            return 1, 1000000, -1000000, 0\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "\n",
    "        res = [0] * 4\n",
    "        if left[0] and right[0] and root.val > left[2] and root.val < right[1]:\n",
    "            res[0] = 1\n",
    "            res[1] = min(left[1], root.val)\n",
    "            res[2] = max(right[2], root.val)\n",
    "            res[3] = left[3] + right[3] + root.val\n",
    "            self.res = max(self.res, res[3])\n",
    "        else:\n",
    "            res[0] = 0\n",
    "        return res\n",
    "\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def isBST(root,min_val,max_val):\n",
    "            if not root:\n",
    "                return True\n",
    "            return min_val < root.val < max_val and isBST(root.left,min_val,root.val) == True and isBST(root.right,root.val,max_val) == True\n",
    "        def tree_sum(rt) -> int:            #当前以rt为root的这棵树的和 \n",
    "            if not rt:\n",
    "                return 0\n",
    "            s = tree_sum(rt.left) + tree_sum(rt.right) + rt.val\n",
    "            self.ans = max(self.ans,s)\n",
    "            return s\n",
    "        def find_max_sum_BST(rt):   #dfs  查找\n",
    "            if isBST(rt,-0x3f3f3f3f,0x3f3f3f3f):\n",
    "                tree_sum(rt)\n",
    "                return\n",
    "            find_max_sum_BST(rt.left)\n",
    "            find_max_sum_BST(rt.right)\n",
    "        self.ans = 0\n",
    "        find_max_sum_BST(root)\n",
    "        return self.ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        def leftmost(node):\n",
    "            while node.left is not None:\n",
    "                node = node.left\n",
    "            return node\n",
    "        \n",
    "        def rightmost(node):\n",
    "            while node.right is not None:\n",
    "                node = node.right\n",
    "            return node\n",
    "        \n",
    "        def search(node) -> Optional[int]:\n",
    "            nonlocal ans\n",
    "            t1 = t2 = 0\n",
    "\n",
    "            if node.left is not None \\\n",
    "              and ((t1 := search(node.left)) is None \\\n",
    "              or node.val <= rightmost(node.left).val):\n",
    "                t1 = None\n",
    "            \n",
    "            if node.right is not None \\\n",
    "              and ((t2 := search(node.right)) is None \\\n",
    "              or node.val >= leftmost(node.right).val):\n",
    "                t2 = None\n",
    "            \n",
    "            if t1 is not None and t2 is not None:\n",
    "                ans = max(ans, t := t1 + t2 + node.val)\n",
    "                return t\n",
    "            \n",
    "            return None\n",
    "\n",
    "        search(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        res=[0]\n",
    "        def func(node):\n",
    "            num = node.val\n",
    "            if not node.left and not node.right:\n",
    "                res[0]=max(res[0],node.val)\n",
    "                return num,num,num\n",
    "            flag = True\n",
    "            m1=n2=num\n",
    "            if node.left:\n",
    "                num1,m1,n1=func(node.left)\n",
    "                if num1 is False or n1 >= node.val:\n",
    "                    flag = False\n",
    "                else:\n",
    "                    num+=num1\n",
    "            if node.right:\n",
    "                num2,m2,n2=func(node.right)\n",
    "                if num2 is False or m2 <= node.val:\n",
    "                    flag = False\n",
    "                else:\n",
    "                    num+=num2\n",
    "            if flag:\n",
    "                res[0] = max(num,res[0])\n",
    "                return num,m1,n2\n",
    "            else:\n",
    "                return False,0,0\n",
    "        func(root)\n",
    "        return res[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree(self, root):\n",
    "        if not root: return [None]*3\n",
    "        sr, ar, br = self.tree(root.right)\n",
    "        sl, al, bl = self.tree(root.left)\n",
    "        if sl=='a' or sr=='a': return 'aaa'\n",
    "        if sr is None and sl is None: \n",
    "            self.res = max(self.res, root.val)\n",
    "            return [root.val]*3\n",
    "        if sr is None:\n",
    "            if bl>=root.val: return 'aaa'\n",
    "            self.res = max(self.res, sl+root.val)\n",
    "            return [sl+root.val, al, root.val]\n",
    "        if sl is None:\n",
    "            if ar<=root.val: return 'aaa'\n",
    "            self.res = max(self.res, sr+root.val)\n",
    "            return [sr+root.val, root.val, br]\n",
    "        if ar<=root.val or bl>=root.val: return 'aaa'\n",
    "        self.res = max(self.res, sr+sl+root.val)\n",
    "        return [sr+sl+root.val, al, br]       \n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.tree(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:return inf, -inf, 0\n",
    "            l_mi, l_mx, l_sum = dfs(node.left)\n",
    "            r_mi, r_mx, r_sum = dfs(node.right)\n",
    "            if node.val <= l_mx or node.val >= r_mi:\n",
    "                return -inf, inf, 0\n",
    "            nonlocal ans\n",
    "            ans = max(ans, l_sum + r_sum + node.val)\n",
    "            return min(l_mi, node.val), max(r_mx, node.val), l_sum + r_sum + node.val\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 使用后序遍历 返回这颗子树的最小节点值 和最大节点值\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return inf, -inf , 0\n",
    "            lmn, lmx, lsumma = dfs(node.left)\n",
    "            rmn, rmx, rsumma = dfs(node.right)\n",
    "            x = node.val\n",
    "            if lmx >= x or rmn <= x:\n",
    "                return -inf, inf ,0\n",
    "            s = lsumma + rsumma + x\n",
    "            nonlocal ans\n",
    "            ans = max(ans,s)\n",
    "            return min(lmn,x), max(rmx, x), s\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValid(self, node):\n",
    "        if node in self.validMemo:\n",
    "            return self.validMemo[node]\n",
    "        if node == None:\n",
    "            return (float('inf'), -float('inf'), True)#min, max, validity\n",
    "        \n",
    "        cur = node.val\n",
    "        leftMin, leftMax, leftVal = self.isValid(node.left)\n",
    "        rightMin, rightMax, rightVal = self.isValid(node.right)\n",
    "        minE = min(cur, leftMin)\n",
    "        maxE = max(cur, rightMax)\n",
    "        validity = leftVal and rightVal and leftMax < cur and rightMin > cur\n",
    "\n",
    "        self.validMemo[node] = (minE, maxE, validity)\n",
    "        return self.validMemo[node]\n",
    "\n",
    "    def recurse(self, root, finalRes):#return result if valid\n",
    "        if root in self.sumMemo:\n",
    "            cur = self.sumMemo[root]\n",
    "            finalRes[0] = max(finalRes[0], cur)\n",
    "            return cur\n",
    "        if root == None:\n",
    "            return 0\n",
    "        cur = root.val\n",
    "        left_val = self.recurse(root.left, finalRes)\n",
    "        right_val = self.recurse(root.right, finalRes)\n",
    "        if self.isValid(root)[-1]:            \n",
    "            result = left_val + right_val + cur\n",
    "            finalRes[0] = max(finalRes[0], result)\n",
    "            self.sumMemo[root] = result\n",
    "            return result\n",
    "        else:\n",
    "            self.sumMemo[root] = 0\n",
    "            return 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        finalRes = [0]\n",
    "        self.validMemo = defaultdict(bool) # node -> bool\n",
    "        self.sumMemo = defaultdict(int) # node -> res\n",
    "        self.recurse(root, finalRes)\n",
    "        # print(self.validMemo)\n",
    "        # print(self.sumMemo)\n",
    "        return max(finalRes[0], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            # Base case: if the node is None\n",
    "            if not node:\n",
    "                return True, 0, float('inf'), float('-inf')\n",
    "\n",
    "            left_is_bst, left_sum, left_min, left_max = dfs(node.left)\n",
    "            right_is_bst, right_sum, right_min, right_max = dfs(node.right)\n",
    "\n",
    "            # Check if the current tree rooted at node is a BST\n",
    "            if left_is_bst and right_is_bst and left_max < node.val < right_min:\n",
    "                self.max_sum = max(self.max_sum, left_sum + right_sum + node.val)\n",
    "                return True, left_sum + right_sum + node.val, min(left_min, node.val), max(right_max, node.val)\n",
    "\n",
    "            # If not a BST, return False and irrelevant values for the other fields\n",
    "            return False, 0, float('-inf'), float('inf')\n",
    "\n",
    "        self.max_sum = 0\n",
    "        dfs(root)\n",
    "        return self.max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxSum = 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.findMaxMinSum(root)\n",
    "        return self.maxSum\n",
    "\n",
    "\n",
    "    def findMaxMinSum(self, root: TreeNode):\n",
    "        \"\"\"\n",
    "\n",
    "        :param root:\n",
    "        :return:\n",
    "        res[0]：root为根的二叉树是否为BST，若为1，则是BST；若为0，则不是BST\n",
    "        res[1]: 记录以root为根的二叉树所有节点的最小值\n",
    "        res[2]: 记录以root为根的二叉树所有节点的最大值\n",
    "        res[1]: 记录以root为根的二叉树所有节点值之和\n",
    "        \"\"\"\n",
    "        # base case\n",
    "        if not root:\n",
    "            return [1, float('inf'), float('-inf'), 0]\n",
    "\n",
    "        # 递归计算左右子树\n",
    "        left = self.findMaxMinSum(root.left)\n",
    "        right = self.findMaxMinSum(root.right)\n",
    "        res = [None] * 4\n",
    "\n",
    "        if left[0] == 1 and left[2] < root.val and right[0] == 1 and right[1] > root.val:\n",
    "            res[0]= 1\n",
    "            # 更新以root为根的这棵BST的最小值\n",
    "            res[1] = min(left[1], root.val)\n",
    "            # 更新以root为根的这棵BST的最大值\n",
    "            res[2] = max(right[2], root.val)\n",
    "\n",
    "            res[3] = left[3] + right[3] + root.val\n",
    "            # 更新全局变量\n",
    "            self.maxSum = max(self.maxSum, res[3])\n",
    "        else:\n",
    "            res[0] = 0\n",
    "        #     其他值没必要计算了，用不到\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        INF = 0x3f ** 0x3f\n",
    "        load = defaultdict(int)\n",
    "        mx, mn = defaultdict(lambda: -INF), defaultdict(lambda: INF)\n",
    "        def recurse(root):\n",
    "            if root.left: recurse(root.left)\n",
    "            if root.right: recurse(root.right)\n",
    "\n",
    "            if root.left and root.right:\n",
    "                if mx[root.left] < root.val < mn[root.right]:\n",
    "                    load[root] += load[root.left] + load[root.right]\n",
    "                else:\n",
    "                    load[root] = -INF\n",
    "            elif root.left and not root.right:\n",
    "                if mx[root.left] < root.val:\n",
    "                    load[root] += load[root.left]\n",
    "                else:\n",
    "                    load[root] = -INF\n",
    "            elif not root.left and root.right:\n",
    "                if mn[root.right] > root.val:\n",
    "                    load[root] += load[root.right]\n",
    "                else:\n",
    "                    load[root] = -INF\n",
    "            mx[root] = max(mx[root.left], mx[root.right], root.val)\n",
    "            mn[root] = min(mn[root.left], mn[root.right], root.val)\n",
    "            load[root] += root.val\n",
    "            return\n",
    "        recurse(root)\n",
    "        return max(max(load.values()), 0)\n",
    "\n",
    "        \n",
    "        # overtime:\n",
    "        # def findMax(root):\n",
    "        #     if root == None:\n",
    "        #         return None\n",
    "        #     rightMAX = findMax(root.right)\n",
    "        #     if rightMAX == None:\n",
    "        #         return root.val\n",
    "        #     else:\n",
    "        #         return rightMAX\n",
    "        \n",
    "        # def findMin(root):\n",
    "        #     if root == None:\n",
    "        #         return None\n",
    "        #     leftMin = findMin(root.left)\n",
    "        #     if leftMin == None:\n",
    "        #         return root.val\n",
    "        #     else:\n",
    "        #         return leftMin\n",
    "        \n",
    "        # def findSum(root):\n",
    "        #     if root == None:\n",
    "        #         return 0\n",
    "        #     leftval = findSum(root.left)\n",
    "        #     rightval = findSum(root.right)\n",
    "        #     # res = root.val + leftval + rightval\n",
    "        #     return root.val + leftval + rightval\n",
    "\n",
    "        # def isBST(root):\n",
    "        #     if root == None:\n",
    "        #         return True\n",
    "        #     if root.left != None and root.val <= root.left.val:\n",
    "        #         return False\n",
    "        #     if root.right != None and root.val >= root.right.val:\n",
    "        #         return False\n",
    "        #     return isBST(root.left) & isBST(root.right)\n",
    "        \n",
    "        # self.res = 0\n",
    "        # def recurse(root):\n",
    "        #     if root == None:\n",
    "        #         return\n",
    "        #     if isBST(root.right) is True and isBST(root.left) is True:\n",
    "        #         lMax, rMin = findMax(root.left), findMin(root.right)\n",
    "        #         res = root.val > lMax if lMax != None else True\n",
    "        #         res &= root.val < rMin if rMin != None else True\n",
    "        #         if res:\n",
    "                    \n",
    "        #             leftSum, rightSum = findSum(root.left), findSum(root.right)\n",
    "        #             rootSum = leftSum + rightSum + root.val\n",
    "        #             self.res = max(rootSum, self.res)\n",
    "        #     recurse(root.left)\n",
    "        #     recurse(root.right)\n",
    "        # recurse(root)\n",
    "        # return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxKeySum = 0\n",
    "\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.maxKeySum\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        isBST = 1\n",
    "        # print('root val', root.val)\n",
    "        if root.left is not None:\n",
    "            leftSum, leftIsBST, leftMin, leftMax = self.traverse(root.left)\n",
    "            if not leftIsBST:\n",
    "                isBST = 0\n",
    "            if leftMax >= root.val:\n",
    "                isBST = 0\n",
    "        else:\n",
    "            leftMin = 100000\n",
    "            leftMax = -100000\n",
    "            leftSum = 0\n",
    "        if root.right is not None:\n",
    "            rightSum, rightIsBST, rightMin, rightMax = self.traverse(root.right)\n",
    "            if not rightIsBST:\n",
    "                isBST = 0\n",
    "            if rightMin <= root.val:\n",
    "                isBST = 0\n",
    "        else:\n",
    "            rightMin = 100000\n",
    "            rightMax = -100000\n",
    "            rightSum = 0\n",
    "\n",
    "        # is a BST now\n",
    "        # print('curnode: %d is BST' % root.val)\n",
    "        if isBST: \n",
    "            keysum = leftSum + rightSum + root.val\n",
    "            if keysum > self.maxKeySum:\n",
    "                self.maxKeySum = keysum\n",
    "        if isBST:\n",
    "\n",
    "            return keysum, True, min(leftMin, root.val), max(rightMax, root.val)\n",
    "        else:\n",
    "            return 0, False, -100000, -100000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxSumBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node)->(bool, int, int, int): #是二叉搜索树，当前的和，最小值，最大值\n",
    "            cur, cur_sum, cur_min, cur_max = True, node.val, node.val, node.val\n",
    "            if node.left:\n",
    "                l, l_sum, l_min, l_max = dfs(node.left)\n",
    "                if not l or l_max >= node.val:\n",
    "                    cur = False\n",
    "                else:\n",
    "                    cur_sum += l_sum\n",
    "                    cur_min = l_min\n",
    "            if node.right:\n",
    "                r, r_sum, r_min, r_max = dfs(node.right)\n",
    "                if not r or r_min <= node.val:\n",
    "                    cur = False\n",
    "                else:\n",
    "                    cur_sum += r_sum\n",
    "                    cur_max = r_max\n",
    "            if cur:\n",
    "                self.ans = max(self.ans, cur_sum)\n",
    "            return cur, cur_sum, cur_min, cur_max \n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
